def is_valid(board, row, col, num):
    # 检查行是否合法
    for i in range(9):
        if board[row][i] == num:
            return False

    # 检查列是否合法
    for i in range(9):
        if board[i][col] == num:
            return False

    # 检查九宫格是否合法
    start_row = 3 * (row // 3)
    start_col = 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False

    return True


def solve_sudoku(board):
    stack = []
    row = 0
    col = 0
    while row < 9:
        if board[row][col] == 0:
            num = 1
            while num <= 9:
                if is_valid(board, row, col, num):
                    board[row][col] = num
                    stack.append((row, col))
                    break
                num += 1

            if num == 10:
                if len(stack) == 0:
                    # 数独无解
                    return False
                else:
                    # 回溯
                    last_row, last_col = stack.pop()
                    board[last_row][last_col] = 0
                    row = last_row
                    col = last_col
                    continue

        col += 1
        if col == 9:
            col = 0
            row += 1

    return True


def print_board(board):
    for i in range(9):
        for j in range(9):
            print(board[i][j], end=" ")
        print()


# 数独示例
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

print("原始数独：")
print_board(board)
print()

if solve_sudoku(board):
    print("解决后的数独：")
    print_board(board)
else:
    print("数独无解")